package map;

import java.util.HashMap;

public class RemoveDuplicateLetters316 {
    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        //计数
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        StringBuilder result = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            //判断result中是否已经存在，有则过，并减少map
            if (result.indexOf(String.valueOf(s.charAt(i))) >= 0) {
                map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
                continue;
            }

            //循环判断前序是否可以删除

            while (result.length() > 0
                    && s.charAt(i) <= result.charAt(result.length() - 1)
                    && map.get(result.charAt(result.length() - 1)) > 1
            ) {
                map.put(result.charAt(result.length() - 1),
                        map.get(result.charAt(result.length() - 1)) - 1);

                result.deleteCharAt(result.length() - 1);

            }
            if (i == s.length() - 1) {
                if (result.lastIndexOf(String.valueOf(s.charAt(i))) < 0) {
                    result.append(s.charAt(i));
                }
            } else {
                result.append(s.charAt(i));
            }
        }
        return result.toString();
    }
}
